package com.demo.java.OD251_300.OD279;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【组装新的数组】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146078662
 */
public class OdMain {
    // 深度优先搜索，遍历所有可能的子集和
    public static int dfs(int[] numbers, int index, int sum, int[][] dp, int targetSum, int minimumNumber) {
        // 如果已经超出边界，返回0
        if (index >= numbers.length) return 0;

        // 如果当前和超出目标和，返回0
        if (sum > targetSum) return 0;

        // 如果当前和满足条件，返回1
        if (sum <= targetSum && targetSum - minimumNumber < sum) return 1;

        // 查找已经计算过的结果
        if (dp[index][sum] != -1) return dp[index][sum];

        int count = 0;
        // 遍历所有可能的子集
        for (int i = index; i < numbers.length; i++) {
            count += dfs(numbers, i, sum + numbers[i], dp, targetSum, minimumNumber); // 累加符合条件的子集
        }

        // 存储当前计算结果，避免重复计算
        dp[index][sum] = count;
        return dp[index][sum];
    }

    public static void main(String[] args) {
        // 输入处理
        Scanner in = new Scanner(System.in);
        int[] numbers = Arrays.stream(in.nextLine().split(" "))  // 将输入的数字转化为数组
                .mapToInt(Integer::parseInt).toArray();
        int targetSum = in.nextInt();  // 目标和

        // 如果输入为空，直接返回0
        if (numbers.length == 0) {
            System.out.println(0);
            return;
        }

        // 初始化dp数组，默认值为-1
        int[][] dp = new int[numbers.length][targetSum + 1];
        Arrays.stream(dp).forEach(row -> Arrays.fill(row, -1));

        // 排序以便早期终止
        Arrays.sort(numbers);
        int minimumNumber = numbers[0]; // 获取最小的数字

        // 调用dfs方法，计算符合条件的子集数量
        try {
            System.out.println(dfs(numbers, 0, 0, dp, targetSum, minimumNumber));
        } catch (Exception e) {
            System.out.println("An error occurred: " + e.getMessage());
        }
    }
}